package demo.practice.leetcode;

public class P654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length==0)
            return null;
        return construct(nums,0,nums.length);
    }

    public TreeNode construct(int[] nums, int l, int r){
        if (l == r)
            return null;
        int max_i = maxIndex(nums, l, r);
        TreeNode root = new TreeNode(nums[max_i]);
        root.left = construct(nums, l, max_i);
        root.right = construct(nums, max_i + 1, r);
        return root;
    }


    private int maxIndex(int[] nums,int i,int j){
        int max= nums[i];
        int index= i;
        for (int k=i+1;k<j;k++){
            if(nums[k]>max){
                max= nums[k];
                index=k;
            }
        }
        return index;
    }
}
